'''
kmp
'''
import random
import string


def kmp_search(s, t):
	m, n = len(s), len(t)

	# 获取跳跃表
	def get_next():
		if n == 1:
			return [-1]
		table = [-1] + [0] * (n - 1)
		i, cn = 2, 0  # [0, i), 最长（前缀和后缀，不包含[0,i)整体[ps:整体与整体必相等]）相等的长度
		while i < n:
			if t[i - 1] == t[cn]:
				table[i] = cn + 1
				i, cn = i + 1, cn + 1
			elif cn > 0:    # cn与i-1匹配不上，但是cn还可以继续往前跳
				cn = table[cn]
			else:           # 0与i-1都匹配不上
				table[i] = 0
				i += 1
		return table

	table = get_next()
	# 匹配主流程
	i, j = 0, 0
	while i < m and j < n:
		if s[i] == t[j]:
			i, j = i + 1, j + 1
		elif j != 0:
			j = table[j]
		else:
			i += 1
	return i - n if j == n else -1      # 如果target匹配完成，否则就是因为s字符串找完了

def compare_method(s, t):
	return s.find(t)

def test_get_next():
	t1 = 'abatabasabatabat'
	t2 = 'abatabasabatabab'
	t3 = 'abatabasabatabaa'
	t4 = 'abatabasabatabaf'
	def get_next(t):
		n = len(t)
		if n == 1:
			return [-1]
		table = [-1] + [0] * (n - 1)
		i, cn = 2, 0  # [0, i), 最长（前缀和后缀，不包含[0,i)整体[ps:整体与整体必相等]）相等的长度
		while i < n:
			if t[i - 1] == t[cn]:
				table[i] = cn + 1
				i, cn = i + 1, cn + 1
			elif cn > 0:    # cn与i-1匹配不上，但是cn还可以继续往前跳
				cn = table[cn]
			else:           # 0与i-1都匹配不上
				table[i] = 0
				i += 1
		return table
	print(get_next(t1))
	print(get_next(t2))
	print(get_next(t3))
	print(get_next(t4))

def test(test_time = 100):
	for _ in range(test_time):
		m,n = random.randint(1,100), random.randint(1,100)
		s = ''.join([random.choice(string.ascii_letters) for _ in range(m)])
		t = ''.join([random.choice(string.ascii_letters) for _ in range(n)])
		r1 = kmp_search(s, t)
		r2 = compare_method(s, t)
		if r1 != r2:
			print('oops!')
			print(s, t)
			print(r1, r2)
			break
	print('测试结束')

if __name__ == '__main__':
	# test_get_next()
	s = 'leetcode'
	t = 'leeto'
	print(kmp_search(s, t))
	print('='*100)
	print()
	test()

